
     1. (Bicicleta lui Andrei). Andrei uraste sa urce. El are o bicicleta pe 
care merge oriunde se poate, alegnd binenteles drumurile cele mai scurte si 
usoare. Partea buna (pentru el): locuieste ntr-un oras, unde toate strazile 
formeaza o retea strict patratica, fiind orientate sau nord-sud (numite bulevarde) 
sau est-vest (numite alei). Deci, distanta ntre orice doua intersectii consecutive 
este aceeasi. Partea rea: orasul este de munte, cu multe strazi n panta si cu 
sens unic. Pentru a ajunge ntr-un anumit loc, Andrei alege totdeauna traseul 
pe baza a trei reguli: 
1. Evita orice strada care urca cu mai mult de 10 m ntre doua intersectii consecutive;
2. Nu foloseste niciodata sensul interzis;
3. Foloseste cel mai scurt drum posibil.
Problema cere sa-l ajutati pe Andrei sa foloseasca un drum acceptabil.

Intrare:
Fisierul de intrare contine datele n urm[toarea forma:
- pe prima linie, doua numere ntregi (n,m) separate prin cel putin un spatiu;
   n reprezinta numarul de alei, iar m, cel de bulevarde (1n,m220).
Pe urmatoarele n linii se afla altitudinile punctelor de intersectie. Fiecare 
linie reprezinta o alee si contine o secventa de m numere ntregi separate prin 
cel putin un spatiu; ele reprezinta altitudinea n metri a punctelor de intersectie 
de pe aleea respectiva. 
  Urmeaza una sau mai multe linii care definesc drumurile cu sens unic. Fiecare 
astfel de drum este reprezentat prin doua perechi de numere intregi separate prin
cel putin un spatiu, sub forma:
	bulevard alee bulevard alee
Drumul cu sens unic porneste din punctul de intersectie al primei perechi si se
incheie in punctul unde se intersecteaza a doua pereche. Daca cele doua puncte 
nu sunt adiacente, drumul cu sens unic va cuprinde si alte intersectii. De exemplu
       5 7 5 10
reprezinta drumurile 5-7 spre 5-8, 5-8 spre 5-9, si 5-9 spre 5-10. Definitiile 
drumurilor se termina cu o linie care contine patru zerouri in formatul anterior.
   In final vor urma una sau mai multe linii care contin perechi de puncte (in
aceeasi reprezentare) intre care Andrei vrea sa gaseasca un drum optim  
Sfarsitul fisierului de intrare este dat de patru zerouri separate prin cel putin
un spatiu.
	Se presupune ca toate bulevardele si toate aleile sunt in domeniile
definite de prima linie a fisierului de intrare, si ca toate drumurile sunt
construite sau pe directia nord-sud, sau est-vest.

Iesirea:
Pentru fiecare drum solicitat de fisierul de intrare, iesirea va lista o
secventa de puncte de la pozitia de pornire la cea finala, formand ruta pe care
o poate urma Andrei, conform conditiilor sale. Doua puncte consecutive de forma
bulevard-alee sunt separate prin cuvantul 'spre'. Daca exista mai multe drumuri
care verifica criteriile lui Andrei, se va lista unul din ele. Daca nu este nici
o solutie sau daca punctul de inceput si cel final coincid, iesirea va fi un mesaj
adecvat.
Doua seturi consecutive de iesiri sunt separate prin cate o linie alba.

Exemplu: Pentru intrarea
3 4
10 15 20 25
19 30 35 30
10 19 26 20
1 1 1 4
2 1 2 4
3 4 3 3
3 3 1 3
1 4 3 4
2 4 2 1
1 1 2 1
0 0 0 0
1 1 2 2
2 3 2 3
2 2 1 1
0 0 0 0
o iesire posibila este:
1-1 spre 1-2 spre 1-3 spre 1-4 spre 2-4 spre 2-3 spre 2-2
Pentru a merge de la 2-3 la 2-3 stai pe loc !
Nu exista drum acceptabil de la 2-2 la 1-1.

=======================================================

	2. (Timp si mobilitate) Sa ne imaginam un aparat care masoara minutele 
scurse prin acumularea unor bile in diverse casute. Sa presupunem ca dispozitivul 
are prevazute 3 casute care masoara un minut, 5 minute si respectiv o ora. 
In decursul unui minut, un brat rotativ misca o bila, o ridica si o depoziteaza 
in una din aceste casute. Dispozitivul este prevazut pentru a masura timpul 
intre 1:00 si 12:59 (fara a indica a.m sau p.m).
De exemplu, 2 bile in indicatorul minut, 6 bile in indicatorul 5-minute si 5 bile
in indicatorul ora, vor reprezenta timpul 5:32.
  Din pacate acest gen de ceas nu poate indica data, desi acest lucru se poate 
deduce; In deplasarea lor, bilele isi schimba pozitia relativa intr-un mod
previzibil, ceea ce poate da informatii despre timpul scurs intre doua pozitii.
mai mult, incepand cu un moment, situatiile incep sa se repete.
  Se cere sa se scrie un program care sa determine timpul scurs pana la prima
repetare a pozitiei, in functie de numarul total de bile care se folosesc.
Operatiile pe care le executa ceasul cu bile:
  - La fiecare minut, bila aflata intr-o stiva este ridicata si depozitata in
casuta care indica un minut si care este capabila sa contina pana la patru bile.
Cand aici vine a cincea bila, greutatea lor face ca fundul cutiei sa se desfaca
si cele patru bilele cad inapoi in stiva; bila care a creat aceasta schimbare
se deplaseaza insa mai departe pana la cutia care indica 5-minute. Aceasta a 
doua cutie poate contine 11 bile; o a 12-a bila cauzeaza rasturnarea inapoi in
stiva a celor 11 bile si rostogolirea celei de-a 12-a in cutia care marcheaza
o ora. Si aceasta a treia cutie poate primi tot 11 bile, dar contine de la 
inceput o bila, astfel incat ora indicata se numara de la 1 la 12. O a 12-a bila
intrata in cutia de 5-minute, dupa ce provoaca golirea acestei cutii, se 
rostogoloeste in cutia corespunzatoare orei, si - fiind si aici depasita capacitatea,
cutia se rastoarna, cele 12 bile revin in stiva si in cutie ramane ultima bila.

Intrare:
Fisierl de intrare defineste o succesiune de ceasuri cu bile, fiecare ceas
lucrand ca mai sus. Ceasurile difera numai prin numarul de bile pe care le are in
stiva la ora 1:00, cand pornesc toate ceasurile. Acest numar este dat pentru 
fiecare ceas, cate unul pe fiecare linie si nu include bila aflata de la inceput
in cutia a treia (pentru ore). Numerele valide sunt in intervalul [27,127].
Sfarsitul fisierului de date este semnalat prin cifra 0 pe o linie.

Iesirea:
Pentru fiecare ceas, programul trebuie sa repeta la iesire numarul de bile (dat
la intrare) urmat de numarul de zile (perioade de 24 ore) scurse pana cand
ceasul ajunge la aceeasi configuratie de la inceput.

Exemplu: Pentru intrarea
30
45
0
   iesirea va fi:
30 bile cicleaza dupa 15 zile.
45 bile cicleaza dupa 378 zile.

==============================================

	3. (Cod Huffman). Problema cere sa se determine o metoda de codificare
a primelor N litere mari din alfabetul sursa (S1..SN), avand frecventele de
aparitie f1..fN, in primele R cifre zecimale T1..TR.
Sa studiem metoda Huffman de codificare in cazul R=2. Procedeul trece prin mai
multi pasi. La fiecare pas se selecteaza doua simboluri din alfabetul sursa avand
cele mai mici frecvente; sa presupunem ca ele sunt S1, S2 si au frecventele f1, f2.
Cele doua simboluri sunt grupate formand o "litera combinata" care apare in alfabetul
sursa cu frecventa f1+f2. Vechile simboluri si frecventele lor sunt eliminate
si procedeul se reia cu noul alfabet, pana cand ramane o singura litera.
Daca in proces sunt mai multe litere cu aceeasi frecventa, alegerea se face
lexicografic. La fiecare pas, celor doua litere selectate pentru a fi combinate
li se asigneaza codul 0 (celei de frecventa minima) respectiv 1; daca frecventele 
sunt egale, se asigneaza 0 primei litere din ordonarea lexicografica.
Codul final pentru fiecare simbol din alfabetul sursa initial se formeaza 
concatenand in ordine inversa cifrele din alfabetul de lucru asignate fiecarei
litere combinate care contine simbolul sursa. 
Exemple:
     Simbol   Frecventa                    Simbol   Frecventa
        A        5                            A        7
        B        7                            B        7
        C        8                            C        7
        D        15                           D        7

Pas 1: A si B grupate                      Pas 1: A si B grupate
Pas 2: C si {A,B} grupate                  Pas 2: C si D grupate
Pas 3: D si {A,B,C} grupate                Pas 3: {A,B} si {C,D} grupate
Codurile rezultate: A=110, B=111,          Codurile rezultate: A=00, B=01,
                    C=10,  D=0                                 C=10, D=11
Lungime medie:(3*5+3*7+2*8+1*15)/35=1.91   Lungime medie:(2*7+2*7+2*7+2*7)/28=2.00

Cand R>2, la fiecare pas se combina R simboluri. Deoarece fiecare pas inlocuieste
efectiv R litere sau litere combinate cu o singura litera combinata, iar ultimul
pas trebuie sa combine R litere sau litere combinate, alfabetul sursa trebuie sa
contina N'=k*(R-1)+R litere, pentru un anumit k>=0 astfel incat N'-N>=0 sa fie
minim. Daca N=N', algoritmul de mai sus se poate aplica similar; altfel alfabetul
sursa se completeaza cu N'-N litere fictive cu frecventa 0. Aceste litere fictive
nu vor fi trecute la iesire.
Sa exemplificam acest caz pentru R=3:

    Simbol   Frecventa
       A        5
       B        7
       C        8
       D       15
Pas 1: ? (litera fictiva), A si B grupate
Pas 2: C, {?,A,B} si D  grupate
Codurile resultate: A=11, B=12, C=0, D=2 (? - de cod 10 se ignora)
Lungime medie:(2*5+2*7+1*8+1*15)/35=1.34

Intrare:
Intrarea va contine cel putin un set de date. Fiecare astfel de set ocupa o linie
din fisierul de intrare si este de forma
R N f1 .. fN
Limite: 1<R<11, 1<N<27, 0<fi<1000
Sfarsitul datelor de intrare este marcat cu cifra 0 pe pozitia lui R; acesta nu
va fi considerat ca un set de date.

Iesire:
Pentru fiecare set de date se scrie pe prima linie numarul lui (numararea este 
secventiala incepand cu 1) si lungimea medie a simbolurilor de lucru (rotunjita
la doua zecimale). Pe fiecare din urmatoarele N linii se scriu literele din
alfabetul sursa (primele N litere mari din alfabetul latin) si codurile Huffman
corespunzatoare, ca in exemplele de mai jos:

Exemple:
Intrare:
2 5 5 10 20 25 40
2 5 4 2 2 1 1
3 7 20 5 8 5 12 6 9
4 6 10 23 18 25 9 12
0
Iesire:
Set 1; lungime medie: 2.10
    A: 1100
    B: 1101
    C: 111
    D: 10
    E: 0

Set 2; lungime medie: 2.20
    A: 11
    B: 00
    C: 01
    D: 100
    E: 101

Set 3; lungime medie: 1.69
    A: 1
    B: 00
    C: 20
    D: 01
    E: 22
    F: 02
    G: 21

Set 4; lungime medie: 1.32
    A: 32
    B: 1
    C: 0
    D: 2
    E: 31
    F: 33
=======================================================

	4. (Concurs marinaresc)

The Atlantic Coastal Mariners (ACM) sailing club is building a race planning
tool to estimate durations of sailboat races with various race courses, wind
directions, and types of sailboats. You must write a program to help with that
task.
A race course is defined by marks with up to 10 marks per race course. A
sailboat must sail to all marks in the specified order. The marks are
identified as x- and y-coordinates on a hypothetical grid with a single unit
equal to one nautical mile (nm). The positive y-axis is oriented due north and
the positive x-axis is oriented due east. The race course is in open waters
without any navigational limitations.
For purposes of this planning tool, the only driving force controlling a 
sailboat is the wind. The wind determines the sailboat's speed of advance and
limits its direction of travel. The wind is constant for the duration of each
race and is specified in terms of the direction from which the wind is blowing
and its speed in nautical miles per hour (kts). Wind direction is specified as
a compass bearing in degrees measured clockwise from 000.0=A1 as north.
Sailboats cannot steer any closer to the wind than a given "point angle" off
the wind direction. In order to make progress closer to the wind direction,
the sailboat must tack back and forth across the wind, steering no closer to
the wind than its point angle. Each time the sailboat tacks or passes a mark
it incurs a tack penalty. For this simulation, each sailboat will travel each
leg of a race (the portion of a race between successive marks) with the
minimum number of tacks and the minimum possible distance. Courses and
directions are specified as compass bearings in degrees measured clockwise
from 000.0 grade as north.
The speed of a sailboat is determined by the sailboat design, wind speed, and
direction steered relative to the wind. In the figure, the wind direction is
45 grade and the point angle is 40 grade. This means then that this sailboat cannot
steer between 5 and 85 because it cannot point that closely into the wind.

For this problem, the ratio of sailboat speed to wind speed is one of three
ratios, selected as shown in the table below according to the angle off the
wind :

    Angle off wind                             Applicable ratio
    >= point angle and < reach angle           point speed ratio
    >= reach angle and < downwind angle        reach speed ratio
    >= downwind angle                          downwind speed ratio

For instance, if the boat is steering at an angle off the wind which is between 
the reach angle and downwind angle then boat speed =3D reach speed ratio * wind
speed

Input
Your solution must accept multiple input data sets. Each data set represents a
different race course to be evaluated for a single sailboat. The data set
begins with a line with 4 numbers: wind direction (real), wind speed (real),
tack penalty (real), and number of marks n (integer). The next line contains
six real numbers: point angle, point speed ratio, reach angle, reach speed
ratio, downwind angle, downwind speed ratio.
The subsequent n lines of the data set represent the n race marks in the order
in which they must be reached. Each line begins with a 2-character mark id
followed by the x-coordinate then y-coordinate of the mark.
The end of input is denoted by a line of four 0's.

Output
The output for your program consists of various data calculated for each input
data set. Values should be presented with the following precisions and units.
    Courses, tacks, directions  0.1 degree    Distance  0.01 nm
    Speed                       0.1 kts       Time      0.01 hours

Output for each race begins with a header containing the number of the data
set (1 for the first, 2 for the second, etc.) and the number of legs. The next
line is the total length of the race course, measured as the sum of distances
between successive marks.
For each leg of the course, the leg number, beginning and ending mark id's,
course from the beginning to end marks of the leg, and the leg distance is
presented. This is followed by a listing of the tacks necessary to complete
the leg. The tacks for each race are numbered sequentially, with tack numbers
beginning with 1 for each race. For each tack, the tack number, the projected
sailboat speed, the course steered, and the length of that tack are presented.
The summary output for each data set includes the total number of tacks, the
total distance traveled for the race, the estimated race duration, and the
total tack penalty time incurred by the sailboat after leaving the first mark.
The exact format of the output is not specified, but all output should be
organized so that it is in the specified order, appropriately labeled and
follows given numeric specifications.

Sample Input
45 10 .1 6
45 0.5 90 0.75 135 0.67
M1 15 10
M2 25 20
M3 22 30
M4 5 25
M5 10 15
M6 10 10
0 0 0 0

Output for the Sample Input
========================
Race 1 has 5 legs
The race layout is  58.48 nm long
-----------------------------

Leg 1 from Mark M1 to M2 =3D=3D > Direction:  45.0  Distance:  14.14 nm
Tack 1 ==> Speed:  5.0   Direction:  90.0  Distance: 10.00 nm
Tack 2 ==> Speed:  5.0   Direction:   0.0  Distance: 10.00 nm=20

Leg 2 from Mark M2 to M3 =3D=3D > Direction: 343.3  Distance:  10.44 nm
Tack 3 ==> Speed:  5.0   Direction: 343.3  Distance: 10.44 nm

Leg 3 from Mark M3 to M4 =3D=3D > Direction: 253.6  Distance:  17.72 nm
Tack 4 ==> Speed:  6.7   Direction: 253.6  Distance: 17.72 nm
Leg 4 from Mark M4 to M5 =3D=3D > Direction: 153.4  Distance:  11.18 nm
Tack 5 ==> Speed:  7.5   Direction: 153.4  Distance: 11.18 nm

Leg 5 from Mark M5 to M6 =3D=3D > Direction: 180.0  Distance:   5.00 nm
Tack 6 ==> Speed:  6.7   Direction: 180.0  Distance:  5.00 nm

--------------------------------
Race 1 was 64.34 nm long with 6 tack legs
Estimated Race Duration is 11.47 hours with 0.50 hours of Tack Penalty

================================================

	5. (Timbre) Filatelistii colectioneaza timbre cu mult timp inainte ca
oficiile postale sa reglementeze utilizarea lor. Un exces de timbre poate crea 
dificultati serviciilor postale dar bucura pe colectionari. Orice serviciu postal
militeaza pentru aplicarea pe plic a unui numar cat mai mic de timbre. Pentru
aceasta vi se cere sa scrieti un program care sa ajute serviciul postal. Marimea 
plicului restrictioneaza numarul de timbre care poate fi lipit pe plic. De exemplu,
daca exista numai timbre de 1 leu si 3 lei si pe un plic se pot lipi maxim 5
timbre, se pot acoperi astfel toate cheltuielile postale intre 1 si 13 lei;

     Cheltuieli   Numar of timbre     Number de timbre
      postale      de 1 leu              de 3 lei    
         1            1                      0
         2            2                      0
         3            0                      1
         4            1                      1
         5            2                      1
         6            0                      2
         7            1                      2
         8            2                      2
         9            0                      3
        10            1                      3
        11            2                      3
        12            0                      4
        13            1                      4

Desi cinci timbre de 3 lei puse pe plic ar aduce postei 15 lei, nu este
posibil sa se puna pe plic timbre in valoare de 14 lei. Deoarece serviciul
postal doreste un interval de costuri postale fara "gauri", el va considera in
acest caz doar un cost postal maxim de 13 lei.

Intrare:
Prima linie a fiecarui set de date contine un intreg S reprezentand numarul
maxim de timbre ce pot fi lipite pe un plic. A doua linie contine un numar N
care arata cate serii de valori de timbre sunt in setul de date. Fiecare din 
urmatoarele N linii contine cate o serie de valori de timbre. Primul numar de
pe linie da numarul de valori al seriei; el este urmat de lista valorilor,
ordonata crescator, ca in exemplu. Fiecare serie are cel mult S valori. Valoarea
maxima a lui S este 10, cea mai mare valoare a unui timbru este 100 iar valoarea 
maxima a lui N este 10. Setul de intrare se termina cu un set de date care incepe
cu 0 (S este 0). 

Iesirea:
Se scoate cate o linie pentru fiecare set de date, care da acoperirea maxima
fara gauri, urmata de seria de timbre care da aceasta acoperire. Formatul de
scriere este:
acoperire maxima = <valoare>: <valorile seriei>
Daca un set de date contine mai multe seturi de valori de timbre care dau aceeasi
acoperire maxima, se va tipari setul cu cel mai mic numar de valori. Daca si aici
avem egalitate, se selecteaza setul cu cea mai joasa valoare maxima.
De exemplu, daca pe plic se pot lipi maxim 5 timbre, atunci seriile 1,4,12,21
si 1,5,12,28 conduc la aceeasi acoperire maxima de 71 lei. Deoarece ambele
serii sunt formate din acelasi numar de timbre (4), al doilea criteriu duce la
alegerea seriei 1,4,12,28.
Daca si dupa acest criteriu raman mai multe solutii posibile, se alege una oarecare.

Exemplu:
Intrare:
5
2
4 1 4 12 21
4 1 5 12 28
10
2
5 1 7 16 31 88
5 1 15 52 67 99
6
2
3 1 5 8
4 1 5 7 8
0
Iesire:
acoperire maxima =  71 :  1  4 12 21
acoperire maxima = 409 :  1  7 16 31 88
acoperire maxima =  48 :  1  5  7  8

==================================================================

	6. (Theseus si Minotaurul)

Those of you with a classical education may remember the legend of Theseus and
the Minotaur. This is an unlikely tale involving a bull-headed monster,
lovelorn damsels, balls of silk and an underground maze full of twisty little
passages all alike. In line with the educational nature of this contest, we
will now reveal the true story.
The maze was a series of caverns connected by passages. Theseus managed to
smuggle into the labyrinth with him a supply of candles and a small tube of
phosphorescent paint with which he could mark his way, or, more specifically,
the exits he used. He knew that he would be lowered into a passage between two
caverns, and that if he could find and kill the Minotaur he would be set free.
His intended strategy was to move cautiously along a passage until he came to
a cavern and then turn right (he was left-handed and wished to keep his sword
away from the wall) and feel his way around the edge of the cavern until he
came to an exit. If this was unmarked, he would mark it and enter it; if it
was marked he would ignore it and continue around the cavern. If he heard the
Minotaur in a cavern with him, he would light a candle and kill the Minotaur,
since the Minotaur would be blinded by the light. If, however, he met the
Minotaur in a passage he would be in trouble, since the size of the passage
would restrict his movements and he would be unable to either light a candle
or fight adequately. When he entered a cavern that had been previously entered
by the Minotaur he would light a candle and leave it there and then turn right
(as usual) but take the Minotaur's exit.
In the meantime, the Minotaur was also searching for Theseus. He was bigger
and slower-moving but he knew the caverns well and hence, unlikely as it may
seem, every time he emerged from a passage into a cavern, so did Theseus,
albeit usually in a different one. The Minotaur turned left when he entered a
cavern and traveled clockwise around it until he came to an unmarked (by him)
exit, at which point he would mark it and take it. If he sensed that the
cavern he was about to enter had a candle burning in it, he would turn and
flee back up the passage he had just used, arriving back at the previous
cavern to complete his 'turn.'
Consider the following labyrinth as an example



Assume that Theseus starts off between A and C going toward C, and that the
Minotaur starts off between F and H going toward H. After entering C, Theseus
will move to D, whereas the Minotaur, after entering H will move to G. Theseus
will then move towards G while the Minotaur will head for D and Theseus will
be killed in the corridor between D and G. If, however, Theseus starts off as
before and the Minotaur starts off between D and G then, while Theseus moves
from C to D to G, the Minotaur moves from G to E to F. When Theseus enters G
he detects that the Minotaur has been there before him and heads for E, and
not for H, reaching it as the Minotaur reaches H. The Minotaur is thwarted in
his attempt to get to G and turns back, arriving in H just as Theseus, still
'following' the Minotaur arrives in F. The Minotaur tries E and is again
thwarted and arrives back at H just as Theseus arrives in hot pursuit. Thus
the Minotaur is slain in H.
Write a program that will simulate Theseus' pursuit of the Minotaur.

Input
Input will consist of a series of labyrinths. Each labyrinth will contain a
series of cavern descriptors, one per line. Each line will contain a cavern
identifier (a single upper case character) followed by a colon (:) and a list
of caverns reachable from it (in counterclockwise order). No cavern will be
connected to itself. The cavern descriptors will not be ordered in any way.
The description of a labyrinth will be terminated by a line starting with a @
character, followed by two pairs of cavern identifiers. The first pair
indicates the passage in which Theseus starts, and the second in which the
Minotaur starts. The travel in a starting passage is toward the cavern whose
identifier is the second character in the pair. The file will be terminated by
a line consisting of a single #.
A final encounter is possible for each input data set.

Output
Output will consist of one line for each labyrinth. Each line will specify who
gets killed and where. Note that if the final encounter takes place in a
passage it should be specified from Theseus' point of view. Follow the format
shown in the example below exactly, which describes the situations referred to
above.

Sample Input
A:BCD
D:BACG
F:HE
G:HED
B:AD
E:FGH
H:FEG
C:AD
@ACFH
A:BCD
D:BACG
F:HE
G:HED
B:AD
E:FGH
H:FEG
C:AD
@ACDG
#
Output for the Sample Input
Theseus is killed between D and G
The Minotaur is slain in H

===================================================

	7 (Trenuri): Sistemul de transport urban a planificat un sistem de transport
intre zona centrala a orasului si suburbii. O parte a acestui proiect consta in
planificarea trenurilor pe diverse rute intre cele mai departate statii si zona
comuna de oprire a metroului.
O buna planificare contine si o faza de simulare a circulatiei ternurilor. O astfel
de simulare consta dintr-o serie de scenarii in care doua trenuri, unul plecand
din statia centrala de metro iar celalalt din cea mai departata statie din suburbii
merg unul spre altul. Scopul este de a afla unde si cand se intalnesc cele doua 
trenuri. Pentru aceasta se cere sa scrieti un program.
Modelul oricarui sistem este construit intr-o varianta simplificata. Toate scenariile
se vor baza pe urmatoarele ipoteze:
1. Timpul de oprire in statii este acelasi.
2. Timpii de accelerare si de franare sunt aceiasi, ca si viteza de rulare.
3. Cand un tren pleaca din statie, el accelereaza (cu o rata constanta) pana
ajunge la viteza maxima. Ramane la aceasta viteza pana cand incepe sa franeze
(cu aceeasi rata constanta) la apropierea statiei urmatoare. Viteza cu care
pleaca un tren din statie si cea cu care ajunge la urmatoarea statie sunt zero
(0.0). Statiile consecutive de pe un traseu sunt suficient de distantate pentru
a permite unui tren sa accelereze pana la viteza maxima si apoi sa franeze.
4. Ambele trenuri din fiecare scenariu pleaca in acelasi moment din cele doua statii.
5. Fiecare traseu are cel mult 30 statii.

Intrare:
Toate valorile de intrare sunt numere reale. Datele pentru fiecare scenariu sunt
in formatul urmator:

d1 d2 ... dn 0.0   Pentru un traseu, lista distantelor (in Km) de la fiecare statie
                   la statia centrala de metrou. Statiile sunt listate in ordinea
                   crescatoare a distantelor, incepand cu cea mai apropiata (statia 1)
                   Toate distantele sunt strict pozitive. Lista se termina cu valoarea
                   0.0
v                  Viteza maxima a trenului, in m/minut.
s                  Acceleratia constanta a trenului m/minut^2.
m                  Numarul de minute cat sta un tren in statie.
Datele de intrare se termina cu un set de date care incepe cu -1.0

Iesirea:
Pentru fiecare scenariu, iesirea consta din urmatoarele date:
1. Numarul secnariului (numararea este consecutiva incepand cu scenariul #1)
2. Timpul scurs (in minute) pana cand cele doua trenuri se intalnesc. Timpii se
dau cu o cifra zecimala. In plus, daca trenurile se intalnesc intr-o statie se
cere numarul statiei unde se intalnesc.
3. Distanta in Km intre statia centrala de metrou si locul unde se intalnesc 
cele doua trenuri. Distantele se exprima cu trei cifre zecimale.

Exemplu:
Date de intrare:
15.0 0.0
5280.0
10560.0
5.0
3.5 7.0 0.0
5280.0
10560.0
2.0
3.4 7.0 0.0
5280.0
10560.0
2.0
-1.0
Raspuns:
Scenariul #1:
   Timpul de intalnire: 7.8 minute
   Distanta: 7.500 Km de la statia centrala de metrou

Scenariul #2:
   Timpul de intalnire: 4.0 minute
   Distanta: 3.500 Km de la statia centrala de metrou, in statia 1

Scenariul #3:
   Timpul de intalnire: 4.1 minutes
   Distanta: 3.400 Km de la statia centrala de metrou, in statia 1

==============================================================================

	8 (Decomprimare) O schema simpla de creare a unei versiuni comprimate pentru
un fisier text fara date numerice poate fi urmatoarea: se face o lista a cuvintelor
din fisierul necomprimat. Orice caracter nealfabetic este copiat direct in fisierul 
comprimat. Un cuvant din fisierul initial este copiat in fisierul comprimat numai
daca apare pentru prima oara; in acest caz el este pus in varful listei.


A simple scheme for creating a compressed version of a text file can be used
for files which contain no digit characters. The compression scheme requires
making a list of the words in the uncompressed file. When a non-alphabetic
character is encountered in the uncompressed file, it is copied directly into
the compressed file. When a word is encountered in the uncompressed file, it
is copied directly into the compressed file only if this is the first
occurrence of the word. In that case, the word is put at the front of the
list. If it is not the first occurrence, the word is not copied to the
compressed file. Instead, its position in the list is copied into the
compressed file and the word is moved to the front of the list. The numbering
of list positions begins at 1.

Write a program that takes a compressed file as input and generates a
reproduction of the original uncompressed file as output. You can assume that
no word contains more than 50 characters and that the original uncompressed
file contains no digit characters.

For the purposes of this problem, a word is defined to be a maximal sequence
of upper- and lower-case letters. Words are case-sensitiveQthe word abc is not
the same as the word Abc. For example,
x-ray             contains 2 words: x and ray
Mary's            contains 2 words: Mary and s
It's a winner     contains 4 words: It and s and a and winner

There is no upper limit on the number of different words in the input file.
The end of the input file is signified by the number 0 on a line by itself.
The terminating 0 merely indicates the end of the input and should not be part
of the output produced by your program.

Sample Input
Dear Sally,

   Please, please do it--1 would 4
Mary very, 1 much.  And 4 6
8 everything in 5's power to make
14 pay off for you.

   -- Thank 2 18 18--
0

Output for the Sample Input
Dear Sally,

   Please, please do it--it would please
Mary very, very much.  And Mary would
do everything in Mary's power to make
it pay off for you.

   -- Thank you very much--
